package fun.coding.leetcode;

public class BalancedBinaryTree {

	public static void main(String[] args) {
		
	}

	
	public boolean isBalanced(TreeNode root) {
		return maxHeight(root) != -1;
	}
	
	// if -1, means it is not a balanced tree, since it will also return the normal height(int), so boolean is not an option. 
	// Kinda of a hack for the return type. 
	public int maxHeight(TreeNode root) {
		if (root == null) return 0;
		
		int l = maxHeight(root.left);
		int r = maxHeight(root.right);
		
		if (l == -1 || r == -1 || Math.abs(l - r) > 1) {
			return -1;
		}
		return Math.max(l, r) + 1;
	}
	
	// This implementation is not the right for balanced tree, it is only about height between the 
	// sub trees, not max and min
	/*    this is a balanced tree
	 *                1
	 *            2      2
	 *          3   3  3
	 *        4   4 
	 */
	public int max = Integer.MIN_VALUE;
	public int min = Integer.MAX_VALUE;
	
	public boolean isBalancedWrong(TreeNode root) {
		helper(root, 0);
		return max - min > 1 ? false : true;
    }
	
	public void helper(TreeNode root, int height) {
		if (root == null) {
			max = Math.max(height, max);
			min = Math.min(height, min);
			return;
		}
	
		height++;
		
		if (root.left == null && root.right == null) {
			max = Math.max(height, max);
			min = Math.min(height, min);
			return;
		}
	
		helper(root.left, height);
		helper(root.right, height);
	}
}
